package 每日签到;

/**
 * @author 陈艺博
 * @date 2021-03-03 21:25
 * @description https://leetcode-cn.com/problems/counting-bits/
 * @解题思路 https://www.yuque.com/u307483/gwlwqe/d0a8d7d5-4040-451f-9edb-7e956f0efd4d
 **/
public class _338_counting_bits_比特位计数 {
    public static void main(String[] args) {
        int[] ints = countBits(5);
        for (int i : ints) {
            System.out.println(i);
        }
    }

    public static int[] countBits(int num) {
        int res[] = new int[num + 1];
        for (int i = 0; i <= num; i++) {
            res[i] = count1(i);
        }
        return res;
    }

    public static int count(int x) {
        return Integer.bitCount(x);
    }

    public static int count1(int num) {
        int count = 0;
        while (num > 0) {
            // 每次消去最后一位的1
            num = num & (num - 1);
            count++;
        }
        return count;
    }
}
